﻿
Namespace std
    'what deque can provide is
    ' 1. o(1) get / set any elements, same as vector, better than list
    ' 2. o(1) add / remove first and last element, same as list, better than vector
    ' but it cannot randomly add / remove elements in the middle

    'from http://www.cplusplus.com/reference/stl/deque/
    'Deque sequences have the following properties:
    '   Individual elements can be accessed by their position index.
    '   Iteration over the elements can be performed in any order.
    '   Elements can be efficiently added and removed from any of its ends
    '       (either the beginning or the end of the sequence).

    'basically, it's a list of arrays. each array has a fixed size.

    Public Class deque(Of T, container As linearContainer(Of array))
        Implements linearContainer(Of T)

        Public Const arraySize As Int64 = 1024
        Private _d As container = Nothing

        Public Class array
            Inherits memblock(Of T)

            Private _count As Int64 = 0

            Public Property count() As Int64
                Get
                    Return _count
                End Get
                Friend Set(ByVal value As Int64)
                    _count = value
                End Set
            End Property

            Public Function full() As Boolean
                Return count() = size()
            End Function

            Public Function empty() As Boolean
                Return count() = 0
            End Function

            Public Sub New()
                MyBase.New()
                size() = arraySize
            End Sub
        End Class

        Public Class iterator
            Inherits randomAccessIterator(Of T)
            Implements container(Of T).iterator

            Private _arrayIt As randomAccessIterator(Of array) = Nothing
            Private _arrayIndex As Int64 = Nothing
            Private _caller As deque(Of T, container) = Nothing

            Public Sub New(ByVal ait As randomAccessIterator(Of array), ByVal aindex As Int64, _
                           ByVal caller As deque(Of T, container))
                copy(_arrayIt, ait)
                copy(_arrayIndex, aindex)
                _caller = caller
            End Sub

            Private Function backward() As Boolean
                If _arrayIndex = 0 Then
                    If _arrayIt <> _caller._d.begin() Then
                        _arrayIt -= 1
                        _arrayIndex = arraySize - 1
                        Return True
                    Else
                        Return False
                    End If
                Else
                    _arrayIndex -= 1
                    Return True
                End If
            End Function

            Private Function forward() As Boolean
                If _arrayIndex = arraySize - 1 Then
                    _arrayIt += 1
                    If _arrayIt <> _caller._d.end() Then
                        _arrayIndex = 0
                        Return True
                    Else
                        Return False
                    End If
                Else
                    _arrayIndex += 1
                    Return True
                End If
            End Function

            Protected Overrides Function traversal(ByVal prev As Boolean) As Boolean
                If prev Then
                    Return backward()
                Else
                    Return forward()
                End If
            End Function
        End Class

        Public Property back() As T Implements backoperatingContainer(Of T).back
            Get

            End Get
            Set(ByVal value As T)

            End Set
        End Property

        Public Function pop_back() As Boolean Implements backoperatingContainer(Of T).pop_back
            Return False
        End Function

        Public Function push_back(ByVal v As T) As Boolean Implements backoperatingContainer(Of T).push_back
            Return False
        End Function

        Public Property at(ByVal index As Long) As T Implements container(Of T).at
            Get

            End Get
            Set(ByVal value As T)

            End Set
        End Property

        Public Sub clear() Implements container(Of T).clear

        End Sub

        Public Function empty() As Boolean Implements container(Of T).empty
            Return False
        End Function

        Public Function insert(ByVal that As T) As container(Of T).iterator Implements container(Of T).insert
            Return Nothing
        End Function

        Public Function size() As Int64 Implements container(Of T).size
            Return npos
        End Function

        Public Property front() As T Implements frontoperatingContainer(Of T).front
            Get

            End Get
            Set(ByVal value As T)

            End Set
        End Property

        Public Function pop_front() As Boolean Implements frontoperatingContainer(Of T).pop_front
            Return False
        End Function

        Public Function push_front(ByVal v As T) As Boolean Implements frontoperatingContainer(Of T).push_front
            Return False
        End Function

        Public Function Clone() As Object Implements System.ICloneable.Clone
            Return Nothing
        End Function

        Public Function begin() As container(Of T).iterator Implements container(Of T).begin
            Return Nothing
        End Function

        Public Function [end]() As container(Of T).iterator Implements container(Of T).end
            Return Nothing
        End Function

        Public Function rbegin() As container(Of T).iterator Implements container(Of T).rbegin
            Return Nothing
        End Function

        Public Function rend() As container(Of T).iterator Implements container(Of T).rend
            Return Nothing
        End Function

        Public Sub New()
            _d = alloc(Of container)()
        End Sub
    End Class
End Namespace
